生物信息學中的序列比對算法可分為以下三類：局部比對算法、全局比對算法和多序列比對算法。以下是這些類型的常見算法以及它們之間的差異，還包括了BWA和BLAST等常見工具。

局部比對算法：

局部比對算法用於在較大的序列中尋找較小序列的局部相似性區域。它們常用於發現序列中的相似片段，例如蛋白質的功能區域或基因的外顯子。常見的局部比對算法包括：

1. Smith-Waterman 算法：這是一種經典的局部比對算法，它運用動態規劃方法找到兩個序列之間的最佳局部對齊。Smith-Waterman算法非常準確，但對於大規模比對來說計算成本高。

2. BLAST（Basic Local Alignment Search Tool）：BLAST是一種高效的局部比對工具，廣泛用於搜索DB中的相似序列。它使用啟發式方法加速比對過程，並生成相似性報告。

3. Bowtie：Bowtie是一種用於DNA序列比對的局部比對工具，它特別適用於短序列比對，如二代定序。

全局比對算法：

全局比對算法將兩個序列的整個長度進行比對，通常用於確定整個序列之間的相似性。它們常用於物種演化分析等應用。常見的全局比對算法包括：

1. Needleman-Wunsch 算法：這是一種經典的全局比對算法，使用動態規劃方法找到兩個序列之間的最佳全局對齊(來計算兩條序列之間的最佳比對)，以最小化編輯距離（也稱為編輯操作的最小數量）。

2. Smith-Waterman 算法：雖然通常用於局部比對，但Smith-Waterman算法也可以用於全局比對，但計算成本高。

多序列比對算法(Multiple Sequence Alignment)：

多序列比對算法用於比對多個序列，通常用於演化分析、基因家族分析等。常見的多序列比對算法包括：

1. ClustalW：ClustalW是一種常用的多序列比對工具，它使用多序列比對算法來確定多個序列之間的相似性。

2. MAFFT：MAFFT是一種高效的多序列比對工具，具有多種比對策略，適用於大規模序列比對。

3. MUSCLE：MUSCLE是另一個常見的多序列比對工具，它具有高度精確的比對能力。

4. T-Coffee：T-Coffee是一種多序列比對工具，它可以整合不同的比對算法的結果，提供更準確的比對。

常見工具：

1. BWA（Burrows-Wheeler Aligner）：BWA是一個用於二代定序數據比對的工具，它基於BWT轉換算法，高效地將测序數據比對到參考基因組。(這工具之後介紹)

2. BLAST（Basic Local Alignment Search Tool）：BLAST是一個廣泛使用的局部比對工具，用於搜索數據庫中的相似序列。

不同的比對算法適用於不同的應用場景，根據你的需求和數據特性，可以選擇適合的比對工具和算法。局部比對算法通常用於快速搜索相似性區域，全局比對算法則用於確定整個序列之間的相似性，而多序列比對算法則用於比對多個序列的演化關係。

Bear的小murmur

題外話，其實Needleman-Wunsch 跟編輯距離的方式類似，只是公式跟代表的意義有些不一樣。